import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        front(list,root);
        String str=list.toString();
        return str.substring(1,str.length()-1);
    }
    public void front(List<Integer> list,TreeNode root){
        if(root==null){
            return;
        }
        front(list,root.left);
        front(list,root.right);
        list.add(root.val);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data==null){
            return null;
        }
        String[] str=data.split(", ");
        Deque<Integer> stack=new ArrayDeque<>();
        int len=str.length;
        for(int i=0;i<len;i++){
            stack.push(Integer.parseInt(str[i]));
        }
        return back(stack,Integer.MIN_VALUE,Integer.MAX_VALUE);
    }

    public TreeNode back(Deque<Integer> stack,int lower,int up){
        if(stack.isEmpty()||stack.peek()<lower||stack.peek()>up){
            return null;
        }
        int value=stack.pop();
        TreeNode root=new TreeNode(value);
        root.left=back(stack,value,up);
        root.right=back(stack,lower,value);
        return root;

    }

}


public class project {
    public String getPermutation(int n, int k) {
        List<Integer> list=new LinkedList<>();
        int product=1;
        for(int i=1;i<=n;i++){
            list.add(i);
            product*=i;
        }
        StringBuilder sb=new StringBuilder();
        for(int i=n;i>=1;i--){
            product/=i;
            int index=(k-1)/product;
            sb.append(list.get(index));
            list.remove(index);
            k%=product;
            if(k==0){
                k=product;
            }
        }
        return sb.toString();
    }



















    public void solveSudoku(char[][] board) {
        solveSudokus(board);
    }

    public boolean solveSudokus(char[][] board){
        int row=board.length;
        int col=board[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                char ch=board[i][j];
                if(ch!='.'){
                    continue;
                }
                for(char value='1';value<='9';value++){
                    if(find(value,i,j,row,col,board)){
                        board[i][j]=value;
                        if(solveSudokus(board)){
                            return true;
                        }
                        board[i][j]='.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    public boolean find(char value,int x,int y,int row,int col,char[][] board){
        for(int i=0;i<row;i++){
            char ch=board[i][y];
            if(ch==value){
                return false;
            }
        }
        for(int i=0;i<col;i++){
            char ch=board[x][i];
            if(ch==value){
                return false;
            }
        }

        int squareRow=(x/3)*3;
        int squareCol=(y/3)*3;
        for(int i=squareRow;i<squareRow+3;i++){
            for(int j=squareCol;j<squareCol+3;j++){
                char ch=board[i][j];
                if(ch==value){
                    return false;
                }
            }
        }
        return true;
    }

}
